//42 - 接雨水
class Solution {
    public int trap(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int prev_Max = 0;
        int suf_Max = 0;
        int ans = 0;
        while(left <= right){
            prev_Max = prev_Max > height[left] ? prev_Max : height[left];
            suf_Max = suf_Max > height[right] ? suf_Max : height[right];
            if(prev_Max < suf_Max){
                ans += prev_Max - height[left];
                left++;
            }else{
                ans += suf_Max - height[right];
                right--;
            }
        }
        return ans;
    }
}
class Solution {
    public int trap(int[] height) {
        int[] prev = new int[height.length];//左边木板的高度
        int[] suf = new int[height.length];//右边木板的高度
        int[] ans = new int[height.length];//左右木板高度的较大值
        int prevMax = 0;
        int sufMax = 0;
        int sum = 0;
        for(int i = 0; i < height.length; i++){
            if(prevMax < height[i]){
                prevMax = height[i];
            }
            prev[i] = prevMax;
        }
        for(int i = height.length - 1; i >= 0; i--){
            if(sufMax < height[i]){
                sufMax = height[i];
            }
            suf[i] = sufMax;
            ans[i] = prev[i]>suf[i]?suf[i]:prev[i];
            sum += ans[i] - height[i];
        }
        return sum;
    }
}
//713
class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if(k <= 1) return 0;
        int n = 0;
        int i = 0;
        int sum = 1;
        for(int j=0; j<nums.length; j++){
            sum *= nums[j];
            while(sum >= k){
                sum /= nums[i];
                i++;
            }
            n += j-i+1;
        }
        return n;
    }
}
public class Test {

}

public class Test {
}
